package com.base.sort.impl;

import com.base.sort.IArraySort;

import java.util.Arrays;

public class InsertSort implements IArraySort {
//    @Override
//    public int[] sort(int[] arr) {
//        int[] array= Arrays.copyOf(arr,arr.length);
//        for (int i = 1; i < array.length; i++) {
//            //记录要插入的数据
//            int tmp = array[i];
//            int j = i;
//            for (; j >0&&tmp<=array[j-1]; j--) {
//                array[j]=array[j-1];
//            }
//            // 如果i与j相等，则表示没有发生插入操作
//            if (i!=j){
//                array[j]=tmp;
//            }
//        }
//        return array;
//    }


    @Override
    public <T extends Comparable<T>> T[] sort(T[] unsorted) {
        T[] ts = Arrays.copyOf(unsorted,unsorted.length);

        for (int i = 1; i < ts.length; i++) {
            T tmp = ts[i];
            int j = i-1;
            for (; j >=0&&tmp.compareTo(ts[j])<0; j--) {
                ts[j+1] = ts[j];


            }
            if (i!=j){
                ts[j+1] = tmp;
            }
        }
        return ts;
    }
}
